package main

import (
	"fmt"
	"math"
)

//#link: https://leetcode-cn.com/problems/form-largest-integer-with-digits-that-add-up-to-target/
func main() {
	cost := []int{4, 3, 2, 5, 6, 7, 2, 5, 5}
	target := 9
	fmt.Println(largestNumber(cost, target))
}

//思路: 先把找到成本在target下的 ，在相同成本下所能构成的数的第一位尽可能大，尽可能多
func largestNumber(cost []int, target int) string {
	//使用前 i 个数位且花费总成本恰好为 j 时的最大位数
	dp := make([][]int, 10)
	//用来记录状态转移过程
	from := make([][]int, 10)
	for i := range dp {
		dp[i] = make([]int, target+1)
		for j := range dp[i] {
			dp[i][j] = math.MinInt32
		}
		from[i] = make([]int, target+1)
	}
	dp[0][0] = 0
	//dp[9][target]用来寻找可以构成的最大位数
	for i, c := range cost {
		for j := 0; j <= target; j++ {
			dp[i+1][j] = dp[i][j]
			if j < c {
				dp[i+1][j] = dp[i][j]
				from[i+1][j] = j
			} else {
				if dp[i][j] > dp[i+1][j-c]+1 {
					dp[i+1][j] = dp[i][j]
					from[i+1][j] = j
				} else {
					dp[i+1][j] = dp[i+1][j-c] + 1
					from[i+1][j] = j - c
				}
			}
		}
	}
	if dp[9][target] < 0 {
		return "0"
	}
	ans := make([]byte, 0, dp[9][target])
	i, j := 9, target
	//用最高位
	for i > 0 {
		if j == from[i][j] {
			i--
		} else {
			ans = append(ans, '0'+byte(i))
			j = from[i][j]
		}
	}
	return string(ans)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
